class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        ans = n - 1
        for i in range(59, 1, -1):
            k = int(pow(n, 1 / i))
            if k > 1:
                v = 1
                mul = 1
                for j in range(1, i + 1):
                    mul *= k
                    v += mul
                if v == n:
                    ans = k
        return str(ans)


if __name__ == "__main__":
    print(Solution().smallestGoodBase("13"))  # "3"
    print(Solution().smallestGoodBase("4681"))  # "8"
    print(Solution().smallestGoodBase("1000000000000000000"))  # "999999999999999999"
